def dfs(n,i,s,is_limit):
    if i==len(n): return s 
    up=int(n[i]) if is_limit else 9
    tmp=0
    for d in range(up+1):
        tmp+=dfs(n,i+1,s+(d==1),is_limit and d==up)
    return tmp

def solve(n):
    return dfs(str(n),0,0,True)

#https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/2681837/shu-wei-dp-tong-yong-mo-ban-fu-ti-dan-py-rsw2/


# def combine(n,k):
#     import math
#     return math.factorial(n)/(math.factorial(k)*math.factorial(n-k))

# def f(k):
#     if k==0: return 0
#     #print([i*combine(k,i)*9**(k-i) for i in range(1,k+1)])
#     return sum([i*combine(k,i)*9**(k-i) for i in range(1,k+1)])

# def solve(n):
#     #print(combine(4,2))
#     k=len(str(n))
#     lst=[int(i) for i in str(n)]
#     print(f(k))

#     #print([((9-lst[i-1]),f(k-i)) for i in range(1,k)])
#     lst1,lst2,lst3,lst4=[],[],[],[]
#     for i in range(k):
#         if i==0:lst1.append(0)
#         else: lst1.append(lst1[-1]+1 if lst[i-1]==1 else lst1[-1])
#         #if lst[i]==0:lst1[-1]+=1
#         lst2.append(f(k-i-1))
#         lst3.append(9-lst[i])
#         lst4.append(lst3[-1]*(lst1[-1]+lst2[-1]))
#         if lst[i]==0: lst4[-1]+=10**(k-i-1)
#     print(lst1,lst2,lst3,lst4)

#     return f(k)-sum(lst4)



print(solve(13))
print(solve(10))
print(solve(0))